This invention relates to the field of telecommunication over a digital network and particularly to the area of application layer multicast (ALM). The invention relates specifically to streaming of data representing video.
Application-layer multicast (ALM) is a technology used to broadcast bulk data over networks. ALM has grown in recent years, making the distribution of bulk data such as multimedia data economically feasible for small companies and even individuals. More recently ALM has been further applied to bandwidth-demanding applications such as video streaming to take advantage of its bandwidth efficiency.
The principle of ALM is to organize participating peers into one or more virtual networks, called overlays, on top of the physical network, and then distribute data along the logical paths in the overlays. Construction of the overlay topology is important to its performance and therefore much research has been done in this area.
Common among many of the existing works is the use of round-trip time (RTT) between peers as the metric in selecting paths for overlay construction. See for example, Y. H. Chu, S. G. Rao, S. Seshan, and H. Zhang, “A Case for End System Multicast,” in IEEE Journal on Selected Areas in Communications, vol. 20, no. 8, October 2002; and S. Banerjee, B. Bhattacharjee, and C. Kommareddy, “Scalable Application Layer Multicast,” in Proceedings of ACM SIGCOMM, August 2002; and D. Tran, K. Hua, and S. Sheu, “Zigzag: An Efficient Peer-To-Peer Scheme for Media Streaming,” in Proceedings of IEEE INFOCOM, 2003. For example, a peer selects a path by choosing the peer with the minimum RTT to forward the data. As peers farther apart geographically tend to have longer RTTs between them, by favoring a short RTT the system can exploit the geographic locality of peers to reduce the number of links that the data must traverse. Moreover, nearby peers are more likely to share high-speed network links, which improves performance further. Finally, RTT can also be used to indirectly detect network congestion as queuing delay during congestion will cause the RTT to increase.
Given the wide-spread adoption of the RTT metric in overlay construction, it is therefore important to investigate its actual performance in path selection. Contrary to common beliefs, it may not always provide accurate estimation of bandwidth availability when used in certain configurations. For example, in one environment, if RTT is used to select between two paths then it will correctly identify the higher-bandwidth path only 67.3% of the time, i.e., slightly better than random.
In addition to the RTT metric, researchers have also employed residual bandwidth in path selection. See for example, John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, and James W. O'Toole, “Overcast: Reliable Multicasting with an Overlay Network,” in Proceedings of the OSDI, October 2000; and X. Xiao, Y. Shi, B. Zhang, and Y. Gao, “OCals: A Novel Overlay Construction Approach for Layered Streaming”, Proc. ICC 2008. Residual bandwidth is defined as the minimum unused capacity of the links along a path and it can be estimated from sending probing packets to the next peer in the overlay topology. An overlay constructed based on residual bandwidth estimations will be very conservative in the sense that it only utilizes the leftover bandwidth in the network for its own data transmissions. This property becomes a strength when the objective is to prevent interference with coexisting traffics, but it will not be suitable for bandwidth-sensitive applications such as video streaming.
More recently an increasing number of ALM protocols began to employ not one, but multiple overlays for data distribution. Multi-overlay ALM protocols can exploit path diversities in the network to de-correlate packet loss [Miguel. Castro, P. Druschel, A. M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, “SplitStream: High-bandwidth Multicast in Cooperative Environments,” in Proceedings of ACM SOSP, October 2003], to explore more available network bandwidth [K. K. To, Jack Y. B. Lee, “Parallel overlays for high data-rate multicast data transfer,” in Computer Networks, 2007], and to increase resilience to local network failures as well as peer churn [V. Venkararaman, Paul Francis, and John Calandrino, “Chunkyspread: Heterogeneous Unstructured End System Multicast,” in Proceedings of IEEE ICNP, November 2006].
In a multi-overlay ALM protocol, the source first splits the original data stream into multiple, say N, sub-streams and then distributes them over the N overlays. Each peer establishes up to N connections to other parent peers according to the overlay topologies to receive and then also forwards the sub-streams to its downstream peers along the overlay networks. Thus each peer is continuously exchanging data with at least N peers. Apart from the data transported, these N connections also provide indirect information of the paths' bandwidth availabilities. This characteristic opened up consideration of an alternative metric for path selection.
Related Work
There are two categories of related work in overlay networks, namely latency-based approaches and bandwidth-based approaches. The focus is in the metrics being used in the construction and adaptation of the overlay topology, and the way such metrics are estimated.
A. Latency-Based Approaches
Latency, typically measured in the form of RTT, has been widely used as the metric for overlay construction. An early study to investigate the feasibility of implementing multicast capability in end hosts resulted in the Narada protocol. Narada first constructs a richer connected graph termed mesh and then builds a spanning tree rooted at the data source by using a variant of a distance-vector routing protocol. Since Narada is designed for delay-sensitive video conferencing applications, the latency of overlay links is used as the primary routing metric to minimize end-to-end delay. The latency is estimated and updated by having peers ping their neighbors periodically. The routing protocol then distributes the latency information so that every host can compute the shortest path (i.e., lowest RTT) to each other.
The NICE protocol was designed to support real-time data applications with large receiver sets, such as news ticker services and stock quotes. In order to keep the control overhead for an average peer constant regardless of system population, the protocol clusters peers into a hierarchy. Peers are clustered according to the distance metric derived from round-trip latency estimations. Latency is estimated by sending a sequence of application-layer probes over UDP and measuring their response times. Each latency estimate is mapped to one of a given set of classes of latency ranges which are then used as the distance metric. The data delivery tree is then constructed from the hierarchy formed.
A topology-aware hierarchical arrangement graph (THAG) [Xing Jin, W.-P. Ken Yiu, S.-H. Gary Chan, Y. Wang, “On Maximizing Tree Bandwidth for Topology-aware Peer-to-Peer Streaming,” in IEEE Transactions on Multimedia, 2007.] is a scheme targeted at live streaming applications. In THAG the adjacent hosts are organized into a group (like the cluster in NICE but much larger), called an arrangement graph (AG), and hosts serve each other within the same group. Since the size of an AG is still limited, a number of AGs are organized into a hierarchical architecture. To reduce propagation delay for live streams, hosts closer (latency-wise) to the source are assigned to higher level AGs. Furthermore, multiple overlay trees are embedded in each AG for data delivery. The trees are constructed in a way similar to SplitStream [Miguel. Castro, P. Druschel, A. M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, “SplitStream: High-bandwidth Multicast in Cooperative Environments,” in Proceedings of ACM SOSP, October 2003], where an interior node in a tree is leaf node in all the other trees.
There are numerous other overlay protocols that employ latency as the metric to construct and maintain their overlay topologies. See, for example, B. Zhang, S. Jamin, and L. Zhang. “Host multicast: A framework for delivering multicast to end users,” in Proceedings of IEEE Infocom, June 2002; and Y. Okada, M. Oguro, J. Katto, and S. Okubo, “A New Approach for the Construction of ALM Trees using Layered Video Coding”, in Proc. P2PMMS, 2005. A survey by Hosseini et al. [M. Hosseini, D. T. Ahmed, S. Shirmohammadi, and N. D. Georganas, “A survey of application-layer multicast protocols,” IEEE Communication Surveys and Tutorials, vol. 9, no. 3, 2007] provides for more comparisons.
B. Bandwidth-Based Approaches
For clarity three types of bandwidth are defined: (a) link bandwidth—the maximum bandwidth capacity of the bottleneck link along a network path; (b) residual bandwidth—the unused bandwidth along a network path; and (c) achievable bandwidth—the data throughput achievable by a given congestion-aware transport protocol (e.g., TCP, TFRC, etc.) along a network path.
Most existing work employed residual bandwidth as the metric for overlay construction. For example, Overcast is an early single-tree ALM protocol designed to maximize bandwidth between receiving hosts and the source at the root of the tree. It employs explicit bandwidth probing to determine the initial location to insert new hosts into the existing tree overlay and also reevaluates the bandwidth availability periodically using probing to adapt to changes in the network.
LION [J. Zhao, F. Yang, Q. Zhang, Z. Zhang, and F. Zhang, “LION: Layered Overlay Multicast With Network Coding,” in IEEE Transactions on Multimedia, 2006] is a more sophisticated ALM protocol that employs multiple overlays for the delivery of multi-layer-encoded data. It builds multiple meshes with each mesh delivering one layer of the encoded data. A receiver subscribes to a selected number of overlays to fully utilize its available bandwidth. The mesh overlays are constructed based on bandwidth information measured using active probing tools.
BARON [Sung-Ju Lee, Sujata Banerjee, Puneet Sharma, Praveen Yalagandula, and Sujoy Basu, “Bandwidth-Aware Routing in Overlay Networks,” in INFOCOM, 2008] is a bandwidth-aware routing scheme for overlay networks that target bandwidth-sensitive applications. When a route between two end hosts is experiencing congestion, BARON finds candidate alternate paths based on link bandwidth and from that selects the best one according to residual bandwidth. Link bandwidth is used for pre-selection because link bandwidth estimates are more stable than residual bandwidth estimates. On the other hand, residual bandwidth estimates are used for the actual selection because it represents the current bandwidth availability.
In another work by Jain and Dovrolis [M. Jain and C. Dovrolis, “Path selection using available bandwidth estimation in overlay-based video streaming,” in Proceedings of the IFIP Networking, 2007] the authors also proposed to use residual bandwidth as the metric in a link-state overlay routing protocol for video streaming. They found that residual bandwidth can result in better video quality compare to other metrics such as loss ratio and jitter. Their residual bandwidth measurement was also in-band using data traffic, but they have only considered overlay networks built by content providers with up to two hops.
C. Other Approaches
Besides latency and bandwidth metrics, ALM protocols based on other metrics have been developed by researchers. For example, Chunkyspread [V. Venkararaman, Paul Francis, and John Calandrino, “Chunkyspread: Heterogeneous Unstructured End System Multicast,” in Proceedings of IEEE ICNP, November 2006] constructs a multi-tree overlay based on data delivery delays. Specifically, the choice of parents is determined by the earliest time at which the parents can forward the same chunk of data. The principle is that parents closer to the source will be able to forward data earlier then others and so are favored by the Chunkyspread protocol.
TAG [M. Kwon, S. Fahmy, “Topology-aware Overlay Networks for Group Communication,” in Proceedings of the NOSSDAV, 2002] exploits knowledge of the physical network topology in constructing its logical overlay tree. The principle is to align the physical and logical topologies so that data will traverse the same path as defined by the routing protocol in the underlying network. If the underlying network's routing protocol is delay-optimized then the resultant overlay tree will also be delay optimized.
A peer in an overlay network is constantly exchanging data with multiple peers, so the actual throughput achieved already provides information on the path bandwidth available. However, unlike file transfer applications such as FTP, video streaming applications typically transfer data at a prescribed data rate rather than as fast as possible. Thus the actual throughput achieved between two peers can only indicate the minimum bandwidth available rather than the maximum bandwidth achievable (unless the throughput is lower than the prescribed video data rate).
For example, suppose the maximum bandwidth achievable between two peers is 1 Mbps, while video data are transferred between the two peers at a prescribed data rate of 1.5 Mbps. In this case, there is clearly not sufficient bandwidth to carry the video stream at the video data rate and so, depending on the implementation of the overlay/transport protocols, either substantial amount of data will be discarded or data delivery will be significantly delayed. Nonetheless, the receiving peer can still measure the throughput of the incoming data, e.g., at about 1 Mbps, to estimate that the path bandwidth is in fact lower than the required video data rate.
On the other hand, if the path bandwidth is higher than the video data rate, e.g., at 3 Mbps versus 1.5 Mbps, the receiving peer will still only measure a throughput of 1.5 Mbps as the sending peer transmit data at the prescribed video data rate. This presents a problem as it means that unused achievable bandwidth in excess of the video data rate is not known to the peers.
What is needed is a new metric for use in path selection and a tool for measurement with the new metric.